#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
	# @param head, a ListNode
	# @return a ListNode
	def insertionSortList(self, head):
		if head is None or head.next is None:
			return head
		HEAD = ListNode(None)
		HEAD.next = head
		front, it = head, head.next
		while it is not None:
			if it.next is not None and it.val > front.val:
				front = it
				it = it.next
			elif front.val < it.val:
				break
			else:
				# move it
				crr = it # crr: carry the number to move
				front.next = it.next
				it = it.next
				p, q = HEAD, HEAD.next
				while p.next.val < crr.val:
					p = p.next
					q = p.next
				crr.next = q
				p.next = crr
		return HEAD.next


if __name__ == '__main__':
	a = ListNode(3)
	b = ListNode(2)
	c = ListNode(4)
	d = ListNode(3)
	a.next = b
	b.next = c


	so = Solution()
	ans = so.insertionSortList(a)
	while ans is not None:
		print ans.val
		ans = ans.next
